
package 二叉树.变历;

import java.util.*;
class ADTtree <Key extends Comparable<Key>,Value>{
    /**
     *
     */
        private Node root;//二叉查找树的根
        private class Node{
            private List<Node> nodeList=null;
            private Key key;
            private Value value;
            private Node lChild,rChild;
            private int N;    //以该节点为根的子树中的结点个数
            //构造方法
            public Node(Key key,Value value,int N) {
                this.key = key;
                this.value =value;
                this.N = N;
            }
            @Override
            public String toString() {
                return "Node [key=" + key + ", value=" + value + ", N=" + N + "]";
            }

        }


    /**
     *
     * @return 返回节点个数
     */
    public int size() {
            return size(root);
        }
        private int size(Node x) {
            if(x==null) {
                return 0;
            }
            return x.N;
        }
        //通过Key查找Value
        public Value search(Key key)  {
            return search(root,key);
        }
        private Value search(Node x,Key key)  {
            //找不到，返回null
            if(x==null) {
                return null;
            }
            //如果不为空，用待查找的值与当前根节点的值进行比较
            int result = key.compareTo(x.key);
            //返回一个整数，大于或小于或等于0
            if(result>0) {
                return search(x.rChild, key);//大于，往右子树递归查
            } else if(result<0) {
                return search(x.lChild, key);
            } else {
                return x.value;
            }
        }

        public void insert(Key key,Value value){
            root = insert(root,key,value);
        }

    /**
     *
     * @param x
     * @param key
     * @param value
     * @return
     * 如果key已经存在，则修改value为新的value值，不存在，则创建一个新的结点
     */
        private Node insert(Node x, Key key, Value value) {

            if(x==null) {
                return new Node(key, value, 1);
            }
            int result = key.compareTo(x.key);
            if(result>0) {
                x.rChild = insert(x.rChild, key, value);
            } else if(result<0) {
                x.lChild = insert(x.lChild, key, value);
            } else {
                x.value = value;
            }
            x.N = size(x.rChild)+size(x.rChild)+1;
            return x;
        }
        //查找最小键
        public Key min() {
            return min(root).key;
        }
        private Node min(Node x) {
            if(x.lChild==null) {
                return x;
            } else {
                return min(x.lChild);
            }
        }
        //二叉查找树中最难的就是删除，先从删最简单的最小结点开始
        public void deleteMin() {
            root = deleteMin(root);
        }
        //返回已经删了最小结点的根节点
        private Node deleteMin(Node x) {
            //在找到最小结点时x时，x=x.right
            if(x.lChild==null) {
                return x.rChild;
            }
            x.lChild = deleteMin(x.lChild);
            x.N = size(x.rChild)+size(x.rChild)+1;
            return x;
        }
        /**删除任意节点
         *   1.如果树为null或者找不到key，返回null
         *   2.否则,通过比较找到键Key的结点:
         *         如果该结点没有右子树 ,只有左子树 x = x.left 
         *         如果该结点没有左子树  ,只有有子树x = x.right
         *         该结点左右子树都有,先用Node t = x 存x结点，
         *         找到以t.right为根节点的树的最小键， 赋予x: x = min(x.right)，及替换x结点
         *         然后把这个最小键删了，把t结点的左子树赋予x.left
         *   3.返回 返回已经删了结点的根节点
         *
         */
        public void delete(Key key) {
            root = delete(root,key);
        }
        private Node delete(Node x, Key key) {
            if(x==null) {
                return null;
            }
            int result = key.compareTo(x.key);
            if(result>0) {
                x.rChild = delete(x.rChild, key);
            } else if(result<0) {
                x.lChild = delete(x.lChild, key);
            } else {
                if(x.rChild==null) {
                    return x.lChild;
                }
                if(x.lChild==null) {
                    return x.rChild;
                }
                Node t = x;
                x = min(t.rChild);
                x.rChild = deleteMin(t.rChild);
                x.lChild = t.lChild;
            }
            x.N = size(x.lChild)+size(x.rChild)+1;
            return x;
        }

        //前序遍历：根--左子树--右子树
        public void preOrder() {
            preOrder(root);
        }


    private void preOrder(Node x) {
            if(x!=null) {
                System.out.print("["+x.key+":"+x.value+"]"+" ");
                preOrder(x.lChild);
                preOrder(x.rChild);
            }
        }
        //中序遍历:左子树--根节点--右子树
        public void inOrder() {
            inOrder(root);
        }
        private void inOrder(Node x) {
            if(x!=null) {
                inOrder(x.lChild);
                System.out.print("["+x.key+":"+x.value+"]"+" ");
                inOrder(x.rChild);
            }
        }
        //后序遍历:左子树--右子树--根节点
        public void postOrder() {
            postOrder(root);
        }
        private void postOrder(Node x) {
            if(x!=null) {
                postOrder(x.lChild);
                postOrder(x.rChild);
                System.out.print("["+x.key+":"+x.value+"]"+" ");
            }
        }

    }

